package Sort;
/**
 * 时间复杂度:
 *      O(nlog2(n))
 * 空间复杂度:
 *      O(1)
 * 稳定性:
 *      不稳定
 */
public class HeapSort {
    public void Sort(int[] array)
    {
        int len = array.length;
        for(int parent = (len - 1 - 1) / 2; parent >= 0; parent--)
        {
            shifDown(array, parent, len);
        }

        len--;
        while (len > 0)
        {
            sawp(array, 0, len);
            shifDown(array, 0, len);
            len--;
        }
    }

    private void shifDown(int[] array, int parent, int len) {
        int child = parent * 2 + 1;
        while (child < len)
        {
            if(child + 1 < len && array[child] < array[child + 1])
            {
                child = child + 1;
            }
            if(array[child] > array[parent])
            {
                sawp(array, parent, child);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }

    private void sawp(int[] array, int parent, int child) {
        int tmp = array[parent];
        array[parent] = array[child];
        array[child] = tmp;
    }
}
